๐งท ๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆ
DP๋ฅผ ํ์ฉํ ์ต๋จ ๊ฒฝ๋ก ํ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ์์ ์ ์ s ์์๋ถํฐ ๋ค๋ฅธ ์ ์ ๋ค๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ๋ค.
- DP๊ฐ ์ ์ฉ๋๋ ์ด์ ๋, ๊ตณ์ด ํ ๋ฒ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๊ณณ์ ๋ค์ ๊ตฌํ ํ์๊ฐ ์๊ธฐ ๋๋ฌธ์ด๋ค.
- ๊ทธ๋ฆฌ๊ณ ์ด๋ฅผ ํ์ฉํด ์ ์ ์์ ์ ์ ๊น์ง ๊ฐ์ ์ ๋ฐ๋ผ ์ด๋ํ ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ตฌํ ์ ์๋ค.
๊ฐ์ ์ ๊ฐ์ด ์์์ธ ๊ฒฝ์ฐ๋ง ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ์ ์๋ค.
์์ ๊ฐ์ ์ด ์กด์ฌํ๋ฉด ์๋๋ ์ด์ ?
- ์ ๊ฒฝ์ฐ, A์์ ์ถ๋ฐํ์ฌ
dist[B] = 10,dist[C] = 4๋ก ์ ๋ฐ์ดํธํ ํ,- ๊ฐ์ฅ ๋น์ฉ์ด ์์ C๋ก ์ด๋ํ ๊ฒ์ด๋ค. ๊ทธ๋ ๊ฒ ๋๋ฉด, ๋ ์ด์ C์ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐฑ์ ๋ ์ผ์ด ์์ด -90์ด ์๋ 4๋ก ์ข ๋ฃ๋๋ค.
ํ์ง๋ง, ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด ๋ฐฉ๋ฌธํ ์ ์ ์ ๋ํด์ ์ฌ๋ฐฉ๋ฌธํ์ฌ ์ต์ ๋น์ฉ์ ์ ์ฅํ๋ค๋ฉด ์์ ๊ฐ์ค์น์ ๋ํ ๊ณ์ฐ์ด ๊ฐ๋ฅํ๋ค. ์ด๋ ์๋์์ ๊ตฌํํ๋ค.
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํ์ ์ํด 2๊ฐ์ง๋ฅผ ์ ์ฅํด์ผ ํ๋ค.
- ํด๋น ์ ์ ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ
- ์ ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ
๐ช ๊ณผ์
- ์ต๋จ ๊ฑฐ๋ฆฌ ๊ฐ์ ๋ฌดํ๋ ๊ฐ์ผ๋ก ์ด๊ธฐํ
- ์์ ์ ์ ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ 0์ด๋ค. (๋ฐฉ๋ฌธ ์ฒ๋ฆฌ)
- ์์ ์ ์ ๊ณผ ์ฐ๊ฒฐ๋ ์ ์ ๋ค์ ์ต๋จ ๊ฑฐ๋ฆฌ ๊ฐ์ ๊ฐฑ์
- ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์ต์์ธ ์ ์ ์ ํ์
- ์ฐพ์ ์ ์ ์ ๋ฐฉ๋ฌธ ์ฒดํฌํ๊ณ , ํด๋น ์ ์ ๊ณผ ์ฐ๊ฒฐ๋ ๋ฏธ๋ฐฉ๋ฌธ ์ ์ ์ ์ต๋จ ๊ฑฐ๋ฆฌ ๊ฐ์ ๊ฐฑ์
- ๋ชจ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ ๋๊น์ง 4~5๋ฒ ๋ฐ๋ณต
๐ช ์๊ฐ ๋ณต์ก๋
- ์ธ์ ํ๋ ฌ ๊ตฌํ ์:
- ์ธ์ ๋ฆฌ์คํธ ๊ตฌํ ์:
๐ช ์ผ์ข ์ ๊ฐ์ ?
์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์ ๋ถํฐ ๋ฐฉ๋ฌธํ ์ ์๋๋ก ํ๋ค.
- ์ฐ์ ์์ ํ์ ์ ์ ์ ๋ฒํธ์ ์ง๊ธ๊น์ง ์ฐพ์๋ธ ํด๋น ์ ์ ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์์ผ๋ก ์ ์ฅํ๋ค.
- ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ค ์์์ ์ผ๋ก๋ถํฐ์ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์ ์ฐพ๋ ๊ณผ์ ์ ๊ฐ๋จํ๊ฒ ํด์ค๋ค.
์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ฐ๋ ์ ์ ์ ์ธํ๋ฉด, BFS์ ๋น์ทํ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ๊ฐ ์ ์ ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ ์ ์งํ๋ฉฐ,
- ์ ์ ๋ฐฉ๋ฌธ๋ง๋ค ์ธ์ ํ ์ ์ ์ ๋ชจ๋ ๊ฒ์ฌํ๋ค.
class Pair implements Comparable<Node> {
int num;
int weight;
public Pair(int num, int weight) {
this.num = num;
this.weight = weight;
}
@Override
public int compareTo(Node n) {
return this.weight - n.weight;
}
}
int V;
ArrayList<ArrayList<Pair>> adjList = new ArrayList<>();
int[] dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Queue<Pair> queue = new PriorityQueue<>();
queue.add(new Pair(src, 0));
while(!queue.isEmpty()) {
Pair p = queue.poll();
int here = p.num;
int cost = p.weight;
if (dist[here] < cost) continue;
for (int i = 0; i < adjList.get(here).size(); i++) {
int there = adjList.get(here).get(i).num;
int nextDist = cost + adjList.get(here).get(i).weight;
if (dist[there] > nextDist) {
dist[there] = nextDist;
queue.add(new Pair(there, nextDist));
}
}
}
}
๐ ์ฐธ๊ณ
- Tech Interview for developer
- [Algorithm] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ : ์์ ๊ฐ์ ์ด ์์ผ๋ฉด ์ ๋๋ ์ด์
- [ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต] ๊ตฌ์ข ๋ง